package dp;

/**
 * leet-code(5) 最长回文子串
 *
 * @author Ringo
 * @date 2021/9/1 8:27
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        String s = "ababaa";
        System.out.println(longestPalindrome(s));
    }

    public static String longestPalindrome(String s) {
        // 只有一个字符必然是回文
        if (s == null || s.length() < 2)
            return s;

        // 有两个字符且前后相等也是回文
        if (s.length() == 2 && s.charAt(0) == s.charAt(1))
            return s;

        int n = s.length();

        // dp[i][j] 表示 s[i...j] 是否是回文串
        boolean[][] dp = new boolean[n][n];

        // 初始化: 单个字符肯定回文串
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }

        int maxLen = 0;
        int start = 0;
        for (int L = 1; L <= n; ++L) {
            for (int i = 0; i < n; ++i) {
                // L = j - i + 1
                int j = L + i - 1;

                if (j >= n) break;

                // s[i] != s[j] 后面不用判断了
                if (s.charAt(i) != s.charAt(j)) continue;

                // L <= 3 肯定是回文串
                // L > 3 才需要判断 dp[i + 1][j - 1]
                if (L > 3 && !dp[i + 1][j - 1]) continue;

                // 这里必然是回文串
                dp[i][j] = true;

                if (L > maxLen) {
                    maxLen = L;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

}
